package br.com.rookgraph;

import br.com.rookgraph.BranchReduce.Aresta;

/**
 * Implementação do Algoritimo de IR. Extraido do artigo: "Abordagem de
 * Refinamento interativo para o problema da árvore geradora com número mínimo
 * de vertices Branches." Diego Mello da Silva
 * 
 * 
 * @author Luan Pontes
 * @since 5-10-12
 * 
 */
public class BranchReduceIR {

	private Graph original;
	private Graph tree;

	public BranchReduceIR(Graph original, Graph tree) {
		super();
		this.original = original;
		this.tree = tree;
	}

	public Graph execute() {

		Graph graphBest = this.tree;

		boolean trocouAresta;
		Aresta lastReplaceAresta = null;
		System.out.println("\n");
		int i = 1;
		do {
			trocouAresta = false;

			Aresta[] listCut = createCuttingList();

			Aresta[] listRep;
			System.out.println("\n Iteração: " + i);
			while (!trocouAresta && listCut.length != 0) {

				Aresta arestCut = selectCutEdge(listCut);

				if (lastReplaceAresta != null
						&& lastReplaceAresta.equals(arestCut)) {
					break;
				}

				System.out.println("Cut: " + arestCut.origin + " <---> " + arestCut.target);

				this.tree.removeEdge(arestCut.origin, arestCut.target);

				listCut = removeArest(arestCut, listCut);

				listRep = createReplacementListToCuttingEdge(arestCut);

				Aresta replace = selectEdgeFromReplamentList(listRep);

				if (replace != null) {

					this.tree.addEdge(replace.origin, replace.target, 1);
					trocouAresta = true;

					lastReplaceAresta = replace;

					System.out.println("Rep: " + replace.origin + " <---> " + replace.target);
					System.out.println("Sigma "	+ this.tree.sigma(replace.origin, replace.target));

					if (this.tree.getBranchs().length > graphBest.getBranchs().length) {

						graphBest = this.tree;

					}
				} else {
					this.tree.addEdge(arestCut.origin, arestCut.target, 1);
				}
			}
			++i;
		} while (trocouAresta);

		return graphBest;
	}

	private Aresta[] removeArest(Aresta arestCut, final Aresta[] list) {
		int count = 0;
		for (int i = 0; i < list.length; i++) {
			if (list[i].equals(arestCut)) {
				list[i] = null;
				count++;
				for (int j = i; j < list.length - 1; j++) {
					list[j] = list[j + 1];
				}
			}
		}
		int length = list.length - count;
		Aresta[] newList = new Aresta[length];
		System.arraycopy(list, 0, newList, 0, length);
		return newList;
	}

	private Aresta selectEdgeFromReplamentList(final Aresta[] listRep) {

		Aresta arestaRep = null;
		int sigma = 1, alfa = -1;

		for (Aresta candidata : listRep) {

			this.tree.addEdge(candidata.origin, candidata.target, 1);

			int alfaCandidata = this.tree.alfa(candidata.origin,candidata.target);
			int sigmaCandidata = this.tree.sigma(candidata.origin,candidata.target);
			
			
			if (alfaCandidata < alfa || alfa == -1) {	
				arestaRep = candidata;
				alfa = alfaCandidata;
				sigma = sigmaCandidata;
			} else if (alfaCandidata == alfa) {

				// se o método for o original usa essa linha abaixo
//				if (sigmaCandidata < sigma) {

 			    // se o método for o modificado usa essa linha abaixo
				if( sigmaCandidata > sigma){

					arestaRep = candidata;
				}
			}

			this.tree.removeEdge(candidata.origin, candidata.target);

		}

		return arestaRep;
	}

	private Aresta[] createReplacementListToCuttingEdge(final Aresta arestaCut) {

		int[] seg1 = this.tree.reached(arestaCut.origin, new int[this.tree.getOrder() - 1]);
		int[] seg2 = this.tree.reached(arestaCut.target, new int[this.tree.getOrder() - 1]);

		// TODO verificar tamanho dessa lista por um teorema.
		Aresta[] arestasRep = new Aresta[seg1.length * seg2.length];

		int count = 0;
		/* Comparar arestas dos segmentos com as do grafo original */

		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {

				final Aresta currentArest = new Aresta(vSeg1, vSeg2);

				if (!currentArest.equals(arestaCut)) {

					if (!this.tree.hasEdge(vSeg1, vSeg2)
							&& this.original.hasEdge(vSeg1, vSeg2)) {

						currentArest.alfa = this.tree.alfa(currentArest.origin,currentArest.target);
						currentArest.sigma = this.tree.sigma(currentArest.origin, currentArest.target);

						// if( currentArest.alfa < arestaCut.alfa){

						arestasRep[count++] = currentArest;
						//							
						// }else if(currentArest.alfa == arestaCut.alfa){
						// if( currentArest.sigma < arestaCut.sigma){
						// arestasRep[count++] = currentArest;
						// }

						// }

					}

				}
			}
		}

		Aresta[] listRep = new Aresta[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para coste.
	 * 
	 * @param listRep
	 * @return
	 */
	private Aresta selectCutEdge(final Aresta[] listCut) {

		int alfaCurrent = -1, alfa = -1, sigmaCurrent = -1;
		Aresta arestaCorte = null;

		for (Aresta arestaCurrent : listCut) {

			alfaCurrent = this.tree.alfa(arestaCurrent.origin,arestaCurrent.target);
			sigmaCurrent = this.tree.sigma(arestaCurrent.origin,arestaCurrent.target);

			if (alfaCurrent > alfa) {

				alfa = alfaCurrent;
				arestaCorte = arestaCurrent;
				arestaCorte.alfa = alfa;
				arestaCorte.sigma = sigmaCurrent;

			} else {
				if (alfaCurrent == alfa) {

				    // execução com IR NORMAL segue linha abaixo
//					arestaCorte = sigmaCurrent > arestaCorte.sigma ? arestaCurrent : arestaCorte;
					
					// execução com IR ALTERADO segue linha abaixo
					arestaCorte = sigmaCurrent < arestaCorte.sigma ? arestaCurrent : arestaCorte;

				}
			}
		}
		return arestaCorte;
	}

	/**
	 * Cria a lista de arestas candidatas a corte.
	 * 
	 * @return
	 */
	private Aresta[] createCuttingList() {
		int order = tree.getOrder();
		int count = 0;
		Aresta[] edgesCut = new Aresta[order * order];

		for (int branch : this.tree.getBranchs()) {
			for (int adjacente : this.tree.getAdjacentes(branch)) {

				Aresta candidata = new Aresta(branch, adjacente);

				if (!conteins(candidata, edgesCut)) {
					edgesCut[count++] = candidata;
				}
			}
		}

		Aresta[] listCut = new Aresta[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		return listCut;
	}

	private boolean conteins(Aresta candidata, Aresta[] edgesCut) {

		for (Aresta aresta : edgesCut) {
			if (aresta != null && aresta.equals(candidata))
				return true;
		}

		return false;
	}

	protected static class Aresta {

		int origin;
		int target;
		int alfa;
		int sigma;

		public Aresta(int origin, int target) {
			this.target = target;
			this.origin = origin;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Aresta) {
				Aresta other = (Aresta) obj;

				return (this.origin == other.origin && this.target == other.target)
						|| (this.origin == other.target && this.target == other.origin);
			}
			return false;
		}
	}
}